package com.clstu.linkedlist;

import sun.security.mscapi.CPublicKey;

import java.util.Stack;

/**
 * 演示单链表的增删改查
 */
public class SingleLikedListDemo {
    public static void main(String[] args) {
        //测试是否写对
        //创建一个 SingleLikedList
        SingleLikedList singleLikedList = new SingleLikedList();
        HeroNode hn1 = new HeroNode(2, "along", "龙王");
        HeroNode hn2 = new HeroNode(8, "jack", "夹克");
        HeroNode hn3 = new HeroNode(9, "mary", "嫁给我");
        HeroNode hn4 = new HeroNode(6, "smith", "神秘人");
        HeroNode hn5 = new HeroNode(1, "alice", "密码学老大");
        SingleLikedList singleLikedList1 = new SingleLikedList();
        HeroNode h1 = new HeroNode(3, "along", "龙王");
        HeroNode h2 = new HeroNode(5, "jack", "夹克");
        HeroNode h3 = new HeroNode(7, "mary", "嫁给我");
        HeroNode h4 = new HeroNode(11, "smith", "神秘人");
        HeroNode h5 = new HeroNode(10, "alice", "密码学老大");
        //添加数据,测试普通添加
//        singleLikedList.add(hn1);
//        singleLikedList.add(hn2);
//        singleLikedList.add(hn3);
//        singleLikedList.add(hn4);
//        singleLikedList.add(hn5);
        //添加数据,测试排序添加
        singleLikedList.addByOrder(hn1);
        singleLikedList.addByOrder(hn2);
        singleLikedList.addByOrder(hn3);
        singleLikedList.addByOrder(hn4);
        singleLikedList.addByOrder(hn5);
        singleLikedList1.addByOrder(h1);
        singleLikedList1.addByOrder(h2);
        singleLikedList1.addByOrder(h3);
        singleLikedList1.addByOrder(h4);
        singleLikedList1.addByOrder(h5);
        //测试修改
        HeroNode along = new HeroNode(1, "阿龙", "新任天下第一");
        singleLikedList.update(along);
        //测试删除
//        singleLikedList.delete(8);
//        singleLikedList.delete(1);
        //看结果
        System.out.println("有序链表1:");
        singleLikedList.list();
        System.out.println("有序链表2:");
        singleLikedList1.list();
        //测试反转链表
//        System.out.println("反转后:");
//        reverseList(singleLikedList.getHead());
//        singleLikedList.list();
//        //测试逆序打印
//        System.out.println("逆序打印:");
//        reversePrint(singleLikedList.getHead());
//        //测试能否求得有效数据个数
//        System.out.println("有效数据个数:"+listSize(singleLikedList.getHead()));
//        //测试倒数第index个数据能否得到
//        System.out.println("倒数:"+getByLastIndex(singleLikedList.getHead(),1));
        //测试排序
        merge(singleLikedList.getHead(),singleLikedList1.getHead());
        System.out.println("排序后:");
        singleLikedList.list();
    }

    //编写方法求单链表中有效节点的个数
    public static int listSize(HeroNode head){
        //如果链表为空
        if (head.next==null) {
            return  0;
        }
        //用计数器遍历求有效节点的个数
        int count = 0;
        HeroNode cur = head.next;//临时变量遍历链表
        while (true){
            //判断是否完
            if(cur == null) {
                return count;
            }
            count++;
            //后移
            cur = cur.next;
        }
    }

    //编写方法得到单链表中倒数index个元素
    public static HeroNode getByLastIndex(HeroNode head,int index){
        //如果链表空,返回null
        if(head.next==null){
            return null;
        }
        //得到链表的size
        int size = listSize(head);
        //根据size判断index是否合法,不合法返回null
        if(index>size||index<=0){
            return null;
        }
        //计算在第几个
        int dex = size - index;
        //遍历改次数,取出对应元素
        HeroNode cur = head.next;
        for (int i = 0; i < dex; i++) {
            cur =cur.next;
        }
        return cur;
    }

    //编写方法将链表逆序(腾讯面试题)
    public static void reverseList(HeroNode head){
        //判断是否空,或者只有一个元素
        if(head.next==null||head.next.next==null){
            return;
        }
        //思路分析:反转头R(相当于是一个头节点,不保存数据,只利用R.next来做引用),cur,next,
        //1.next = cur.next;   保存next,因为下一步要把next指向前面去了
        //2.cur.next = R.next; 原本R.next保存的是cur的前一个元素
        //3.R.next = cur ,     R.next后移
        //4.cur = next;      //cur后移
        //5.最后一步,用head 取代 R
        //定义变量
        HeroNode reverseHead = new HeroNode(0, "", "");//反转头
        HeroNode cur = head.next;
        HeroNode next = null;//用来保存cur原本的next
        //循环反转
        while (cur != null){
            next = cur.next;
            cur.next = reverseHead.next;//把next指针指向前面一个元素,实现反转
            reverseHead.next = cur;//保存的就是下一轮cur的前一个元素
            cur = next;
        }
        //注意不能写成head = reverseHead,这里的head只是对对象的一个引用,出了这个方法这个head就引用不了了,所以必须修改对象本身的内容才行
        head.next = reverseHead.next;
    }

    //编写方法实现单向链表的逆序打印,不能破坏链表结构(百度面试题)
    public static void reversePrint(HeroNode head){
        //思路分析,利用栈结构的先进后出的特点实现逆序打印
        //判断是否链表空
        if(head.next == null){
            return;
        }
        //1.所有数据遍历入栈
        HeroNode cur = head.next;//
        Stack<HeroNode> ss = new Stack<>();
        while (true){
            //如果遍历完
            if(cur==null){
                break;
            }
            //入栈
            ss.push(cur);
            //后移
            cur= cur.next;
        }
        //2.所有数据出栈,同时打印,就实现了逆序
        while (ss.size()>0){
            System.out.println(ss.pop());
        }
    }

    //编写方法实现合并两个单向链表,合并后的链表依然有序,且head1是合并后的链表头(经典面试题)
    public static void merge(HeroNode head1,HeroNode head2){
        //判断head1是否空
        if(head1==null){
            head1.next = head2.next;
            return;
        }
        //判断head2是否空
        if(head2==null){
            return;
        }
        //思路分析,用newHead 来当做新头节点,循环比较两边的cur设更小,更小的就添加到newHead尾部并且后移,然后新链表cur0辅助变量也随之后移
        //   2.用head1 取代 newHead
        //定义辅组变量
        HeroNode newHead = new HeroNode(0, "", "");//新头
        HeroNode cur1 = head1.next;//遍历head1
        HeroNode cur2 = head2.next;//遍历head2
        //1.确认新的头部
        if(cur1.id<cur2.id){
            newHead.next = cur1;
            cur1 = cur1.next;
        }else {
            newHead.next = cur2;
            cur2 = cur2.next;
        }
        HeroNode cur0 = newHead.next;//记录新尾节点
        //2.遍历比较插入
        while (true){
            //如果遍历完
            if(cur1 == null){
                cur0.next = cur2;
                break;
            }
            if(cur2 == null){
                cur0.next = cur1;
                break;
            }
            //比较插入到新的尾部
            if(cur1.id<cur2.id){
                cur0.next = cur1;//必须写
                cur1 = cur1.next;//后移
            }else {
                cur0.next = cur2;
                cur2 = cur2.next;//后移
            }
            //新的尾部后移
            cur0 = cur0.next;
        }
        //3.用head1取代newHead
        head1.next = newHead.next;
    }
}
/**
 * heroNode 一个对象就是一个节点
 */
class HeroNode{
    public int id;//编号
    public String name;//姓名
    public String nickName;//别名
    public HeroNode next;//next

    //构造器
    public HeroNode(int id, String name, String nickName) {
        this.id = id;
        this.name = name;
        this.nickName = nickName;
    }

    //为了显示方便,重写toString方法
    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\''+
                '}';
    }
}

/**
 * 链表类,管理HeroNode
 */
class SingleLikedList{
    //先初始化一个头节点,头节点不要动,不保存数据,只用于引用.
    private HeroNode head = new HeroNode(0,"","");

    public HeroNode getHead() {
        return head;
    }

    //编写方法添加节点(不排序)
    public void add(HeroNode heroNode){
        //1.找到尾节点
        HeroNode tmp = head;//tmp便于遍历,头节点不能动
        while (true){
            //如果找到最后
            if(tmp.next == null){
                break;
            }
            //后移遍历链表
            tmp = tmp.next;
        }
        //循环结束后tmp就是最后一个节点了
        //2.将节点插入到最后即可
        tmp.next = heroNode;
    }

    //编写方法排序添加,如果编号存在则不能添加
    public void addByOrder(HeroNode heroNode){
        //1.找到插入的位置
        HeroNode tmp = head;
        while (true){
            //如果遍历完
            if(tmp.next == null){
                break;
            }
            //如果找到合适位置
            if(tmp.next.id > heroNode.id){
                break;
            }
            //如果不能添加
            if(tmp.next.id == heroNode.id){//如果要用next.id判断就保存同一都用这个判断
                System.out.println("编号已经存在,不能添加,失败");
                return;
            }
            //后移
            tmp = tmp.next;
        }
        //循环结束一定是可以插入的位置
        //2.插入
        heroNode.next = tmp.next;
        tmp.next = heroNode;
    }

    //编写方法显示整个链表
    public void list(){
        //判断链表是否空
        if(head.next==null){
            System.out.println("链表空,无数据");
            return;
        }
        //循环遍历显示整个链表即可
        HeroNode tmp = head.next;//头节点不能动,于是用临时变量来遍历
        while (true){
            //如果到最后了
            if(tmp == null) return;
            //显示节点信息
            System.out.println(tmp);
            //后移
            tmp = tmp.next;
        }
    }

    //编写方法修改链表的信息(根据编号)
    public void update(HeroNode heroNode){
        //判断链表是否空
        if(head.next==null) {
            System.out.println("链表空,修改失败");
            return;
        }
        //1.找到修改的位置
        HeroNode tmp = head.next;//头节点不能动,用临时变量来遍历
        boolean find = false;//用于判断是否找到
        while (true){
            //如果遍历完(避免空指针异常需要先判断,注意!!!)
            if(tmp == null){
                break;
            }
            //如果找到
            if (heroNode.id == tmp.id){
                find=true;
                break;
            }
            //后移
            tmp = tmp.next;
        }
        //判断是否找到
        if(find){
            //修改信息
            tmp.name = heroNode.name;
            tmp.nickName = heroNode.nickName;
        }else {
            //没找到
            System.out.println("没有找到编号信息,修改失败");
        }
    }

    //编写方法删除节点,根据id
    public void delete(int id){
        //判断链表是否空
        if (head.next==null){
            System.out.println("链表空,删除失败");
            return;
        }
        //1.找到删除的位置
        HeroNode tmp = head;
        boolean find = false;//是否找到
        while (true){
            //如果遍历完
            if(tmp.next ==null){
                break;
            }
            //如果找到
            if(id== tmp.next.id){
                find = true;
                break;
            }
            //后移
            tmp=tmp.next;
        }
        //判断是否找到
        if (find){
            //如果找到
            //被删除的节点将在没有变量指向它,会被垃圾回收机制自动回收
            tmp.next = tmp.next.next;
        }else {
            System.out.println("未找到改编号,删除失败");
        }
    }

}